//题目:
// 给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

// 示例 1：
// 输入：matrix =[[0,1,1,1],[1,1,1,1],[0,1,1,1]]
// 输出：15
// 解释： 
// 边长为 1 的正方形有 10 个。
// 边长为 2 的正方形有 4 个。
// 边长为 3 的正方形有 1 个。
// 正方形的总数 = 10 + 4 + 1 = 15.

// 示例 2：
// 输入：matrix = [[1,0,1],[1,1,0],[1,1,0]]
// 输出：7
// 解释：
// 边长为 1 的正方形有 6 个。 
// 边长为 2 的正方形有 1 个。
// 正方形的总数 = 6 + 1 = 7.
 
// 提示：
// 1 <= arr.length <= 300
// 1 <= arr[0].length <= 300
// 0 <= arr[i][j] <= 1
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int countSquares(vector<vector<int>>& matrix) 
    {
        int m=matrix.size(),n=matrix[0].size();
        //1.创建dp表————dp[i][j]表示：以matrix[i][j]位置为右下角的正方形个数
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        //2.初始化————暂无
        //3.填表————动态转移方程:dp[i][j]
        int ret=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(matrix[i-1][j-1]==1) dp[i][j]=1;
                int min_len=min(dp[i-1][j],dp[i][j-1]);

                if(matrix[i-1][j-1]==1 && min_len>=1 && matrix[i-min_len-1][j-min_len-1]==1)
                    dp[i][j]+=min_len;
                else if(matrix[i-1][j-1]==1 && min_len>=1)
                    dp[i][j]+=(min_len-1);

                ret+=dp[i][j];//统计结果
            }
        }
        //4.确定返回值
        return ret;
    }
};